package main

func main() {
	root := &TreeNode{
		Val: 8,
		Left: &TreeNode{
			Val:   -70,
			Left:  nil,
			Right: nil,
		},
		Right: &TreeNode{
			Val:   81,
			Left:  nil,
			Right: nil,
		},
	}
	println(lowestCommonAncestor(root, 31))
}

// 搜索树：左节点小于root，右节点大于root。而且左边所有的值都要小于root值，右边所有节点值都大于根节点值
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {

	node := root
	for {
		if node == nil {
			return root
		}

		if node.Val > p.Val && node.Val > q.Val {
			node = node.Left
			continue
		}

		if node.Val < p.Val && node.Val < q.Val {
			node = node.Right
			continue
		}

		return node
	}

	return root
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
